package kyssion.leetcode.num51_100;

public class code81_搜索旋转排序数组2 {
    public static void main(String[] args) {
//        System.out.println(new code81_搜索旋转排序数组2().search(new int[]{
//                2, 5, 6, 0, 0, 1, 2
//        }, 2));
//        System.out.println(new code81_搜索旋转排序数组2().search(new int[]{
//                1,1
//        }, 6));
//        System.out.println(new code81_搜索旋转排序数组2().search(new int[]{
//                1,3
//        }, 6));
//        System.out.println(new code81_搜索旋转排序数组2().search(new int[]{
//                1,3
//        }, 3));
//        System.out.println(new code81_搜索旋转排序数组2().search(new int[]{
//                3,1
//        }, 3));

        System.out.println(new code81_搜索旋转排序数组2().search(new int[]{
                1,1,3,1
        }, 3));

    }

    public boolean search(int[] nums, int target) {
        if (nums.length == 0) {
            return false;
        }
        return find(nums, 0, nums.length - 1, target);
    }

    public boolean find(int[] nums, int start, int end, int target) {
        if (start == end) {
            return nums[start] == target;
        }
        if(start>end){
            return false;
        }
        int midle = (start + end) >> 1;
        if (nums[midle] > target) {
            if (nums[midle] >= nums[end]) {
                return find(nums, start, midle - 1, target) ||
                        find(nums, midle + 1, end, target);
            } else {
                return find(nums, start, midle, target);
            }
        } else if (nums[midle] < target) {
            if (nums[midle] > nums[end]) {
                return find(nums, midle + 1, end, target);
            } else  {
                return find(nums, midle + 1, end, target) || find(nums, start, midle - 1, target);
            }
        } else {
            return true;
        }
    }
}
